16: Graph Representations

Storing Graphs: List vs. Matrix

The practical application of graph algorithms hinges on how efficiently the structure $G=(V, E)$ is stored in memory. We primarily utilize two representation methods, tailored for different graph densities:

Adjacency List: An array (indexed by vertex $v \in V$ ) where each entry points to a linked list (or dynamic array) containing the neighbors of $v$ . $L[v] \rightarrow \{ u_1, u_2, \dots, u_{\text{degree}(v)} \}$
- Benefit: Space efficient for sparse graphs ( $m \ll n^2$ ). Fast iteration over neighbors.
Adjacency Matrix: An $n \times n$ Boolean array $A$ , where $A[i][j] = 1$ if there is an edge $(v_i, v_j)$ , and $0$ otherwise.
- Benefit: Extremely fast $O(1)$ edge existence lookup. Simple implementation.

Representation Trade-offs

Let $n = |V|$ and $m = |E|$ . Understanding the computational trade-offs is crucial for algorithm design.

Feature	Adjacency List	Adjacency Matrix
Space Complexity	$O(n + m)$	$O(n^2)$
Check Edge $(u, v)$	$O(\text{degree}(u))$	$O(1)$
Iterate Neighbors of $u$	$O(\text{degree}(u))$	$O(n)$
Best Use Case	Sparse Graphs ( $m \ll n^2$ )	Dense Graphs ( $m \approx n^2$ )

📝 Interactive Checkpoint

Consider a network graph $G$ with $|V| = 10,000$ vertices and $|E| = 20,000$ edges. This graph is highly sparse.

1. Which representation minimizes memory usage for this specific graph?

A) Adjacency List
B) Adjacency Matrix
C) Both use comparable space

2. What is the time complexity to check if an edge $(u, v)$ exists using an Adjacency Matrix?

A) $O(n)$
B) $O(\log n)$
C) $O(1)$
D) $O(\text{degree}(u))$

Now, consider a dense social network with 1,000 users where nearly everyone is connected to everyone else ( $m \approx n^2$ ).

3. Which representation's space complexity becomes more acceptable or even preferable?

A) Adjacency List
B) Adjacency Matrix
C) Neither is suitable

4. For finding all friends of a user (iterating neighbors) in a sparse graph, why is an Adjacency List faster?

A) It only processes actual neighbors, not all possible vertices.
B) It uses less memory, which always makes it faster.
C) Matrix lookups are inherently slow.

KEY TIPS

💡 Key Tips

Weighted Graphs

For weighted graphs, store weights instead of booleans. In a matrix, A[i][j] = weight. In a list, store tuples: (neighbor, weight).

Undirected vs. Directed

For an undirected graph, an adjacency matrix is symmetric (A[i][j] == A[j][i]), meaning you store each edge's information twice.

Pythonic Lists

A Pythonic way to build an adjacency list is with collections.defaultdict(list), which avoids key-checking boilerplate.

Implicit vs. Explicit

Some graphs, like grids, can be represented implicitly. You can calculate neighbors on-the-fly instead of storing them, saving significant memory.